package strategies;

import java.util.ArrayList;
import java.util.Collection;
import java.util.HashMap;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;
import java.util.Map.Entry;
import java.util.Stack;

import plots.Plot;
import utils.Debug;

import agents.*;
import agents.AverageUtility.UtilityComparator;
import base.Environment;


/**
 * A generic strategy generator.
 */
public abstract class StrategyGenerator {

	protected final static int MIN_RATIO_NO = 2;
	
	protected Environment env;
	
	
	public StrategyGenerator(Environment env) {
		this.env = env;
	}
	
	
	public Environment getEnvironment() {
		return env;
	}

	/**
	 * Generates an initial strategy according to this generator's specific implementation.
	 * 
	 * @param agent the agent for which to generate the strategy
	 * 
	 * @return a new strategy
	 */
	public abstract Strategy genStrategy(Agent agent);
	
	/**
	 * Generates an initial strategy according to this generator's specific implementation.
	 * 
	 * @param targets the number of units to harvest from individual plots
	 * 
	 * @return a new strategy
	 */
	public abstract Strategy genStrategy(int[] targets);
	
	/**
	 * Updates the specified agent's strategies' harvesting targets according to this generator's
	 * specific implementation.
	 * 
	 * @param agent the agent to update
	 */
	public abstract void updateStrategiesTargets(Agent agent);
	
	/**
	 * Updates the specified agent's strategies' paths according to this generator's specific
	 * implementation.
	 * 
	 * @param agent the agent to update
	 * @param number the number of strategies to generate
	 * 
	 * @return modified versions of existing strategies
	 */
	public abstract List<Strategy> updateStrategiesPaths(Agent agent, int number);
	
	/**
	 * Updates a single strategy by modifying the existing plots' targets.
	 *  
	 * @param strategy - the strategy to be altered
	 */
	protected abstract void updateStrategyTargets(Strategy strategy);
	
	/**
	 * Updates a single strategy by eliminating useless plots from the path, and adding others.
	 *  
	 * @param strategy - the strategy to be altered
	 * 
	 * @return the new version of the strategy
	 */
	protected abstract Strategy updateStrategyPaths(Strategy strategy);
	
	/**
	 * Generates a new path with a target value of 0 for all nodes.
	 * 
	 * @param length the length of the path
	 * 
	 * @return a new path
	 */
	protected abstract LinkedList<PlotTarget> genPath(int length);
	
	/**
	 * Generates a new path with the specified target values for the respective nodes.
	 * 
	 * @param targets the harvest target values
	 * 
	 * @return a new path
	 */
	protected abstract LinkedList<PlotTarget> genPath(int[] targets);
	
	/**
	 * Generates a new path with the specified target values for the respective nodes.
	 * 
	 * @param plotTargets the plot and target pairs to be included in the path
	 * 
	 * @return a new path
	 */
	protected abstract LinkedList<PlotTarget> genPath(List<PlotTarget> plotTargets);
	
	/**
	 * Generates a path that has specified targets for specified plots
	 * Using a DFS from the first plot to generate this path; 
	 * 		the special kind of DFS with a lil' extra on the side 
	 * 
	 * @param plots - to be harvested
	 * @param targets - for each plot
	 * @return the constructed plot
	 */
	protected LinkedList<PlotTarget> genPath(Plot[] plots, int[] targets){
		LinkedList<PlotTarget> result = new LinkedList<PlotTarget>();
		HashMap<Plot, PlotTarget> plTMap = new HashMap<Plot, PlotTarget>();
		
		//	Create intended plotTargets
		for(int i=0; i<plots.length; i++)
			plTMap.put(plots[i], new PlotTarget(plots[i], targets[i]));
		
		ArrayList<Plot> visitedPs = new ArrayList<Plot>();
		Stack<Plot> st = new Stack<Plot>();
		st.add(plots[0]);
		
		
		while (!plTMap.isEmpty()){
			Plot currPlot = st.peek();
			if (!visitedPs.contains(currPlot))
				visitedPs.add(currPlot);
			
			//	Add new plot to path
			PlotTarget newPlT = plTMap.remove(currPlot);
			if (newPlT == null)
				newPlT = new PlotTarget(currPlot, 0);
			result.add(newPlT);
			
			//	Select future plot to explore
			Plot futureP = null;
			for(Plot x:env.getPlots().getNeighbors(currPlot))
				if (plTMap.get(x) != null){
					futureP = x;
					break;
				} else if (!visitedPs.contains(x))
					futureP = x;
			
			if (futureP != null)
				st.add(futureP);
			else 
				st.pop();			
		}
		
		return result;
	}
	
	/** 
	 * Detects which strategies should be path-updated
	 * Can be implemented right here - it is not StrategyGenerator-type specific 
	 * 
	 * @param agent - the agent whose Strategies to select for update 
	 * @return list of picked strategies
	 */
	protected ArrayList<Strategy> pickStrategiesToUpdate(Agent agent) {
		ArrayList<Strategy> result = new ArrayList<Strategy>(agent.getStrategies().keySet());
		result.removeAll(pickStrategiesToDelete(agent));
		return result;
	}
	
	/** 
	 * Detects which strategies should be completely deleted - thus making room for new ones
	 * Can be implemented right here - it is not StrategyGenerator-type specific
	 * 
	 * @param agent - the agent whose Strategies to select for deletion
	 * @return list of picked strategies
	 */
	public ArrayList<Strategy> pickStrategiesToDelete(Agent agent) {		
		double stdDev = computeStdDeviation(agent);
		return pickStrategies(agent, AverageUtility.INCREASING_UTILITY_COMPARATOR, stdDev);		
	}
	
	/**
	 * Generic strategies extraction function 
	 * @param agent
	 * @param order - from where to extract strategies - top or bottom
	 * @param sigma - width from peak in which the agent utilities will be
	 * @return -ArrayList of extracted strategies
	 */
	protected ArrayList<Strategy> pickStrategies(Agent agent,
												 UtilityComparator comparator,
												 double sigma) {
		
		ArrayList<Strategy> result = new ArrayList<Strategy>();
		LinkedList<Entry<Strategy, AverageUtility>> sortedStrats =
				agent.getSortedStrategies(comparator);
		double threshold = sortedStrats.peek().getValue().getAverageUtility() + comparator.order * sigma;
		
		while (!sortedStrats.isEmpty() &&
			   sortedStrats.peek().getValue().getAverageUtility() * comparator.order <
			   threshold * comparator.order)
			result.add(sortedStrats.poll().getKey());
		
		System.out.println("for order " + comparator.order + " chose " + result.size() + " strats");
		Debug.pauseExec();

		return result;
	}	
	
	private double computeStdDeviation(Agent agent){
		double result = 0, avg = 0;	
		Collection<AverageUtility> stratUtilities = agent.getStrategies().values();
		
		for(AverageUtility x:stratUtilities) {
			avg += x.getAverageUtility();
		}
		avg /= stratUtilities.size();
		
		for(AverageUtility x:stratUtilities)
			result += Math.pow(x.getAverageUtility() - avg, 2);
		result = Math.sqrt(result / stratUtilities.size());
		
		return result;
	}
	
	
	protected static void unveilPath(Strategy s){
		for(Iterator<PlotTarget> it = s.path.iterator(); it.hasNext();)
			System.out.print(it.next() + " ");
		System.out.println();
	}
}
